package tree;

import java.util.*;

public class BinaryTreeOerations {
    //通过一棵树的结点，来在逻辑上表示一棵树
    public static TreeNode createBinaryTree(){
        TreeNode a = new TreeNode('A');     //char 类型转为 int ，保存的是 Unicode 码
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        //创建结点之间的关系
        //左孩子或者右孩子为 null 时可以不写
        a.left = b; a.right= c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        d.left = null; d.right = null;
        e.left = null; e.right = h;
        f.left = null; f.right = null;
        g.left = null; g.right = null;
        h.left = null; h.right = null;

        //返回根节点
        return a;
    }

    static int count;
    //统计结点个数:该方法的弊端是在每一次调用前都需要手动对 count 赋值为0，不然 count 会一直累加
    private static void countNode(TreeNode root){
        //root == null 不进行统计
        if(root == null){
            return;
        }
        //每经过这里一次就进行一次记录
        count++;//count 的生命周期需要跨方法存在(方法结束生命周期也需要存在)
                //变量：对一块内存空间的抽象
                //变量的生命周期：这块内存能生存多久
                //不能使用局部变量，局部变量随着方法的执行而存在
        //进行递归
        countNode(root.left);
        countNode(root.right);
    }

    //使用聚合的思想统计结点的个数:这种方法不需要对统计结点个数的变量手动赋值为0
    public static int getNodeSize(TreeNode root){
        if(root == null){
            //空树
            return 0;
        }
        //分别统计结点的两个字数的结点个数
        int leftTreeNodeSize = getNodeSize(root.left);
        int rightTreeNodeSize = getNodeSize(root.right);

        //进行汇总聚合
        //最终的结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1 (根结点)
        return leftTreeNodeSize + rightTreeNodeSize + 1;
    }


    //前序遍历(递归)
    private static void preorder(TreeNode root) {
        // 空树的前序遍历，什么都不做
        // 当根结点是 null 时，直接含义：根结点不存在；间接含义：树的空树
        if (root == null) {
            // 代表要遍历的树是空树
            return;
        }
        //前序：根 左 右

        // 说明这棵树不是空树
        // 1) 先处理根结点：当下的意义：打印当前结点中的元素
        System.out.printf("%s\n", root.toString());
        // 2) 采用相同的方式进行左子树的处理
        // 什么叫做采用相同的方式？ 递归调用 preorder() 方法
        // 应该传入的实参是什么？需要传入左子树 -> 左子树的根结点 -> 当前根结点的左孩子结点 -> root.left
        preorder(root.left);

        // 3) 采用相同的方式进行右子树的处理
        preorder(root.right);
    }

    //前序遍历 非递归
    public static void preorder2(TreeNode root){
        //用栈来存放二叉树的结点，方便回溯
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        //循环停止的条件 cur == null && stack.isEmpty()
        //必须是 && ，当 cur == null 时，栈中还有结点的右子树未处理
        while(cur != null || stack.isEmpty() == false){
            while(cur != null){
                System.out.println(cur.toString());
                stack.push(cur);
                cur = cur.left;
            }
            //依次从栈中弹出
            TreeNode top = stack.pop();
            //处理右子树
            cur = top.right;
        }
    }

    //中序遍历(递归)
    private static void inorder(TreeNode root){
        if(root == null){
            return ;
        }
        //中序：左 根 右
        inorder(root.left);
        System.out.printf("%s\n",root.toString());
        inorder(root.right);
    }

    //中序遍历 非递归
    public static void inorder2(TreeNode root){
        //用栈来存放二叉树的结点，方便回溯
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || stack.isEmpty() == false){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //依次从栈中弹出元素，处理剩下没走的右子树
            TreeNode top = stack.pop();
            System.out.println(top);
            cur = top.right;
        }
    }
    //后序遍历(递归)
    private static void postorder(TreeNode root){
        if(root == null){
            return ;
        }
        //后序：左 右 根
        postorder(root.left);
        postorder(root.right);
        System.out.printf("%s\n",root.toString());
    }

    //后序遍历 非递归
    public static void postorder2(TreeNode root){
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode last = null;

        while(cur != null || stack.isEmpty() == false){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //查看栈顶元素
            TreeNode top = stack.peek();
            if(top.right == null){
                System.out.println(top);
                last = top;
                stack.poll();
            }else if(top.right == last){
                System.out.println(top);
                last = top;
                stack.pop();
            }else{
                cur = top.right;
            }
        }
    }
    static int leafCount;
    //统计叶子结点的个数:与统计结点个数相同，存在弊端
    //用遍历的思想查看二叉树中的结点个数
    private static void preorderCountLeafNode(TreeNode root){
        if(root == null){
            return ;
        }
        //先处理根这时，root 代表的不是一棵树的根结点，而是仅仅被当成遍历时经过的某个结点
        //叶子节点：不存在左孩子和右孩子
        if(root.left == null || root.right == null){
            leafCount++;
        }
        preorderCountLeafNode(root.left);
        preorderCountLeafNode(root.right);
    }

    //利用聚合的思想统计叶子结点的个数
    public static int getLeafNodeSize(TreeNode root){
        if(root == null){
            //空树,无结点
            return 0;
        }
        //在这里 root 代表的是一棵树的根结点
        if(root.left == null || root.right == null){
            //根的左孩子不存在 且 根的右孩子也不存在
            //说明这个 root 为根的树只有一个结点
            //只有一个结点的树，这个根结点就是唯一的一个叶子结点，所以叶子结点个数就是 1 个
            return 1;
        }
        //聚合的思路
        int leftSize = getLeafNodeSize(root.left);
        int rightSize = getLeafNodeSize(root.right);

        return leftSize + rightSize;
    }

    //统计第K层上的结点
    public static int getKLevelNodeSize(TreeNode root,int k){
        if(k < 1){
            throw new RuntimeException("错误的层数k");
        }
        if(root == null){
            //当空树时，无论求第几层，结点的个数都是 0 个
            return 0;
        }
        //root != null
        if(k == 1){
            //只有一层，所以只有一个结点，即根结点
            return 1;
        }
        //剩余的情况可以根据对左子树和右子树的递归进行
        int leftgetKLevelNodeSize = getKLevelNodeSize(root.left,k - 1);
        int rightgetKLevelNodeSize = getKLevelNodeSize(root.right,k - 1);
        //递归的过程中，k 的值在逐渐变小
        //意味着一定会走到 root == null 或者 k == 1 的情况
        return leftgetKLevelNodeSize + rightgetKLevelNodeSize;
    }

    //求二叉树的高度
    public static int getHeightOf(TreeNode root){
        if(root == null){
            //空树
            return 0;
        }
        //可有可无
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftHeight = getHeightOf(root.left);
        int rightHeight = getHeightOf(root.right);
        return Integer.max(leftHeight,rightHeight) + 1;
    }

    //判断二叉树中是否包含某个值
    public static boolean contains(TreeNode root,int target){
        if(root == null){
            return false;
        }
        //root != null
        //按照前序遍历的方式进行查找：根 -> 左子树 -> 右子树
        //这个遍历可能不会全部走完，遇到 target 相同的值就直接返回true

        //判断根结点是不是
        if(root.value == target){
            return true;
        }

        //root != null && root.value != target
        //在左子树中查找
        boolean r = contains(root.left,target);
        if(r == true){
            return true;
        }
        r = contains(root.right,target);
        if(r == true){
            return true;
        }else{
            return false;
        }
        //可以直接写成这种方式：
//        return root.value == target || contains(root.left,target) || contains(root.right,target);
    }

    //判断二叉树中是否包含某个结点
    public static boolean containsNode(TreeNode root,TreeNode targetNode){
        if(root == null){
            return false;
        }
        //同一性的比较：
        //root 和 targetNode 是不是同一个结点(逻辑)
        //root 引用和 targetNode 引用是否指向的时同一个 TreeNode 对象
        //使用 == 比较
        if(root == targetNode){
            //root 和 targetNode 指向了同一个对象
            //二叉树的根结点就是要找的结点
            return true;
        }
        boolean r = containsNode(root.left,targetNode);
        if(r == true){
            return true;
        }
        r = containsNode(root.right,targetNode);
        if(r == true){
            return true;
        }else{
            return false;
        }
        //可以直接写成这样：
//        return root == targetNode || containsNode(root.left,targetNode) ||containsNode(root.right,targetNode);
    }

    //返回包含 target 的结点
    public static TreeNode nodeOf(TreeNode root,int target){
        if(root == null){
            return null;
        }
        //按照前序遍历的顺序来找
        if(root.value == target){
            //找到了包含 target 的结点
            return root;
        }
        //根里没有就去左子树继续查找
        //需要根据左子树的查找结果来判断是否找到，所以需要保存左子树查找的结果
        TreeNode r = nodeOf(root.left,target);
        //判断是否在左子树中找到包含 target 的结点
        //用 root != null 进行判断
        if(r != null){
            //说明在左子树中找到了，返回包含 target 的结点
            //现在 r 这个引用指向了包含 target 的结点
            return r;
        }
        //根没有，左子树也没有，在右子树进行查找
        r = nodeOf(root.right,target);
        if(r != null){
            return r;
        }else{
            return null;//代表没有找到
        }
    }

    //层序遍历
    public static void levelorder(TreeNode root){
        if(root == null){
            return;
        }
        //用队列的思想，将结点先放到队列中，取出该结点时将它的左右孩子也放进去
        Queue<TreeNode> queue = new LinkedList<>();
        //将根结点放入队列中，层序遍历不会把 null 放入队列，所以不用考虑 root 是否为 null
        queue.offer(root);
        //开始循环
        //当队列不为空时，就将结点的左右孩子放进去
        while(queue.isEmpty() == false){
            //1.取出队首元素
            TreeNode node = queue.poll();
            //node 一定不为 null
            //2.打印结点的值
            System.out.println(node.toString());
            //3.依次从左到右把孩子放入队列，不放 null 进去
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
    }

    //用层序遍历来统计二叉树的结点个数
    public static int sizeOf(TreeNode root){
        if(root == null){
            return 0;
        }
        //用队列，用层序遍历的方式将所有结点都放到队列中，然后出队
        //每出一个结点，就 size++
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int size = 0;
        while(queue.isEmpty() == false){
            TreeNode node = queue.poll();
            size++;
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return size;
    }

    //用层序遍历来统计二叉树叶子结点的个数
    public static int leafSizeOf(TreeNode root){
        if(root == null){
            return 0;
        }
        //与用层序遍历统计二叉树结点个数方法基本相同
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int size = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left == null && node.right == null){
                //当左右孩子都为 null 时，说明时叶子结点
                size++;
            }
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return size;
    }

    //打印出结点和结点所在的层
    //需要将结点和层数打包在一起输出
    //定义一个类，对 node 和 level 进行输出和初始化
    static class TreeNodeWithLevel{
        public TreeNode node;
        public int level;
        public TreeNodeWithLevel(TreeNode node,int level){
            this.node = node;
            this.level = level;
        }

        @Override
        public String toString() {
            return String.format("%s-%d",node.toString(),level);
        }
    }
    //打印结点和层数的方法
    public static void levelOrderButLevel(TreeNode root){
        if(root == null){
            return;
        }
        //进行层序遍历
        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root,1));
        while(!queue.isEmpty()){
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;
            System.out.println(tnwl);
            if(node.left != null){
                queue.offer(new TreeNodeWithLevel(node.left,level + 1));
            }
            if(node.right != null){
                queue.offer(new TreeNodeWithLevel(node.right,level + 1));
            }
        }
    }

    //打印出结点和结点所在的层,第二种方法
    public static void levelOrderButLevel2(TreeNode root){
        if(root == null){
            return;
        }
        //用两个队列，一个存放结点，另一个存放层数
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();

        nodeQueue.offer(root);
        levelQueue.offer(1);

        //必须保证 nodeQueue 和 levelQueue 的元素个数是一样的
        //所以，只需要判断其中一个是否为 null
        while(!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();

            System.out.println(node + "-" + level);

            if(node.left != null){
                nodeQueue.offer(node.left);
                levelQueue.offer(level + 1);
            }
            if(node.right != null){
                nodeQueue.offer(node.right);
                levelQueue.offer(level + 1);
            }
        }
    }

    //用层序遍历的方法统计第 k 层的结点个数
    public static int getKLevelSize(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root,1));
        int size = 0;
        while(!queue.isEmpty()){
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;
            if(level == k){
                size++;
            }
            if(node.left != null){
                queue.offer(new TreeNodeWithLevel(node.left,level + 1));
            }
            if(node.right != null){
                queue.offer(new TreeNodeWithLevel(node.right,level + 1));
            }
        }
        return size;
    }

    //用层序遍历计算二叉树的高度
    public static int heightOf(TreeNode root){
        if(root == null){
            return 0;
        }
        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root,1));
        int height = 0;
        while(!queue.isEmpty()){
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;

            height = level;

            if(node.left != null){
                queue.offer(new TreeNodeWithLevel(node.left,level + 1));
            }
            if(node.right != null){
                queue.offer(new TreeNodeWithLevel(node.right,level + 1));
            }
        }
        //在循环的过程中 height 一直在更新，最后一个 height 是最后一层的层数 level
        return height;
    }

    //用层序遍历的方式判断是否是完全二叉树
    public static boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        //循环停止的条件是从队列中取出的元素是 null
        while(true){
            TreeNode node = queue.poll();
            if(node == null){
                break;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        //检查队列中是否还有 !null 的情况
        //如果有，则说明不是完全二叉树
        //如果没有，则说明是完全二叉树
        //所以，遍历队列中剩下的元素
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        TreeNode root = createBinaryTree();
        System.out.println("测试叶子结点个数：");
        leafCount = 0;
        preorderCountLeafNode(root);

        leafCount = 0;
        preorderCountLeafNode(root);

        leafCount = 0;
        preorderCountLeafNode(root);

        int size = getLeafNodeSize(root);
        System.out.println(size);

        preorder(root);
        System.out.println("---------");
        inorder(root);
        System.out.println("---------");
        postorder(root);
        System.out.println("---------");

        System.out.println("测试查找k层的结点个数：");
        System.out.println(getKLevelNodeSize(root,1));  //1
        System.out.println(getKLevelNodeSize(root,2));  //2
        System.out.println(getKLevelNodeSize(root,3));  //4
        System.out.println(getKLevelNodeSize(root,4));  //1
        System.out.println(getKLevelNodeSize(root,5));  //0
        System.out.println(getKLevelNodeSize(root,6));  //0
        System.out.println("---------");

        System.out.println("测试二叉树高度：");
        int h = getHeightOf(root);
        System.out.println(h);
        System.out.println("---------");

        System.out.println("测试层序遍历");
        levelorder(root);
        System.out.println("---------");

        System.out.println("测试用层序遍历统计结点个数");
        System.out.println(sizeOf(root));
        System.out.println("---------");

        System.out.println("测试用层序遍历统计叶子结点个数");
        System.out.println(leafSizeOf(root));
        System.out.println("---------");

        System.out.println("测试打印结点和结点层数");
        levelOrderButLevel(root);
        System.out.println("---------");
        levelOrderButLevel2(root);
        System.out.println("---------");

        System.out.println("测试第 k 层的结点个数");
        System.out.println(getKLevelSize(root,3));
        System.out.println("---------");

        System.out.println("测试二叉树的高度");
        System.out.println(heightOf(root));
        System.out.println("---------");

        System.out.println("测试是否是完全二叉树");
        System.out.println(isCompleteTree(root));
        System.out.println("---------");

        System.out.println("测试前序遍历");
        preorder(root);
        System.out.println("---------");
        preorder2(root);
        System.out.println("---------");

        System.out.println("测试中序遍历");
        inorder(root);
        System.out.println("---------");
        inorder2(root);
        System.out.println("---------");

        System.out.println("测试后序遍历");
        postorder(root);
        System.out.println("---------");
        postorder2(root);
        System.out.println("---------");
    }
}
